class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        dp = [{"()"}]
        for i in range(1, n):
            dp.append(set())
            for j in range(i + 1 >> 1):
                for p in dp[j]:
                    for q in dp[i - j - 1]:
                        dp[i].add(p + q)
                        dp[i].add(q + p)
            for j in dp[i - 1]:
                dp[i].add(f"({j})")
        return list(dp[-1])
